359,数据结构-3,队列
基础知识
队列是一种特殊的线性表,他的特殊性在于我们只能操作他头部和尾部的元素,中间的元素我们操作不了,我们只能在他的头部进行删除,尾部进行添加。就像大家排队到银行取钱一样,先来的肯定要排到前面,后来的只能排在队尾,所有元素都要遵守这个操作,没有VIP会员,所以走后门插队的现象是不可能存在的,他是一种先进先出的数据结构。我们来看一下队列的数据结构是什么样的
1,一般队列
他只能从左边进,右边出,队列实现方式一般有两种,一种是基于数组的,还一种是基于链表的,如果基于链表的倒还好说,因为链表的长度是随时都可以变的,这个实现起来比较简单。如果是基于数组的,就会稍微有点不同,因为数组的大小在初始化的时候就已经固定了,我们来看一下基于数组的实现,假如我们初始化一个长度是10的队列
front指向的是队列的头,tail指向的是队列尾的下一个存储空间,最初始的时候front=0,tail=0,每添加一个元素tail就加1,每移除一个元素front就加1,但是这样会有一个问题,如果一个元素不停的加入队列,然后再不停的从队列中移除,会导致tail和front越来越大,最后会导致队列无法再加入数据了,但实际上队列前面全部都是空的,这导致空间的极大浪费。我们自己来写一个简单的队列看一下
1public class MyQueue<E> {
2
3 private final Object[] data;
4 private final int maxSize;
5 private int size;
6 private int front = 0;
7 private int tail = 0;
8
9 public MyQueue(int maxSize) {
10 if (maxSize <= 0) {
11 throw new IllegalArgumentException("队列容量必须大于0 : " + maxSize);
12 }
13 this.maxSize = maxSize;
14 data = new Object[this.maxSize];
15 }
16
17 public void add(E e) {
18 if (isFull()) {//这地方可以扩容也可以抛异常,为了方便这里我们就不在扩容了。
19 throw new IllegalStateException("队列已经满了,无法再加入……");
20 }
21 data[tail++] = e;
22 size++;
23 }
24
25 public E remove() {
26 if (isEmpty()) {
27 throw new IllegalStateException("队列是空的,无法移除……");
28 }
29 E t = (E) data[front];
30 data[front++] = null;
31 size--;
32 return t;
33 }
34
35 //队列头和队列尾指向同一空间的时候,并且没到队尾,表示队列是空的
36 public boolean isEmpty() {
37 return front == tail && !isFull();
38 }
39
40 public boolean isFull() {//最后一个位置是不存储数据的
41 return tail == maxSize - 1;
42 }
43
44 public int getSize() {
45 return size;
46 }
47}
代码非常简单,当然队列的实现不一定是这一种方式,比如我们可以让tail指向队尾的元素,或者以链表的形式来实现都是可以的,不同的实现方式会导致上面的方法有所不同。我们来测试一下
1public static void main(String[] args) {
2 MyQueue myQueue = new MyQueue(10);
3 System.out.println("isEmpty()=" + myQueue.isEmpty());
4 System.out.println("isFull()=" + myQueue.isFull());
5 System.out.println("getSize()=" + myQueue.getSize());
6 for (int i = 0; i < 9; i++) {
7 myQueue.add(i * 100);
8 myQueue.remove();
9 }
10 System.out.println("----------------------------");
11 System.out.println("isEmpty()=" + myQueue.isEmpty());
12 System.out.println("isFull()=" + myQueue.isFull());
13 System.out.println("getSize()=" + myQueue.getSize());
14}
看一下打印的结果
1 isEmpty()=true
2 isFull()=false
3 getSize()=0
4 ----------------------------
5 isEmpty()=false
6 isFull()=true
7 getSize()=0
我们添加了9次,然后又移除了9次,结果队列竟然满了,如果我们再添加一次的话肯定会抛异常,但实际上队列的size是0,还是空的,也就是说数组的每个位置只能使用一次,这样就造成了极大的浪费。那么前面使用过的空间还能不能再次利用了呢,实际上是可以的,我们可以把队列看成是环形的,当tail到达数组末尾的时候,如果数组的前面有空位子,我们可以让tail从头开始,这个时候一个新的队列就产生了,那就是双端队列。
2,双端队列
双端队列也是有两个指针,front指向队首,tail指向队尾的下一个存储单元,并且双端队列的队首和队尾都可以添加和删除元素,我们来看一下图
这样空间就可以循环利用了,不会造成浪费,我们来看下代码
1public class MyQueue<E> {
2
3 //存储的元素
4 private Object[] data;
5
6 //指向队列头,这个头并不是数组的第0个元素,如果这样
7 // front就没有意义了,这个从下面的addFirst(E e)方
8 // 法也可以看出,如果当front等于0的时候,在添加到
9 // first,那么会添加到数组的末尾,并且front也指向
10 // 数组的末尾
11 private int front;
12
13 //指向队列尾的下一个空间,可以这样理解,front指向
14 // 的是第一个元素,tail指向的是最后一个元素的下一
15 // 个,指的是空的。
16 private int tail;
17
18
19 public MyQueue(int numElements) {
20 data = new Object[numElements];
21 }
22
23 //空间扩容,我们这里选择扩大一倍,当然也可以选择其
24 // 他值,仅仅当满的时候才能触发扩容, 这时候front
25 // 和tail都会指向同一个元素
26 private void doubleCapacity() {
27 int p = front;
28 int n = data.length;//数组的长度
29 //关键是r不好理解,举个例子,在数组中,front
30 // 不一定是之前0位置的,他可以指向其他位置,
31 // 比如原来空间大小为16,front为13,也就是第
32 // 14个元素(数组是从0开始的),那么r就是16-13=3,
33 // 也就是从front往后还有多少元素,待会copy的时候
34 // 也是先从最后的r个元素开始
35 int r = n - p;
36 Object[] a = new Object[n << 1];//扩大一倍
37 System.arraycopy(data, p, a, 0, r);//先copy后面的r个
38 System.arraycopy(data, 0, a, r, p);//再copy前面的p个
39 data = a;
40 //重新调整front和tail的值
41 front = 0;
42 tail = n;
43 }
44
45 public void addFirst(E e) {
46 //添加到front的前面,所以front-1
47 front = (front - 1 + data.length) % data.length;
48 data[front] = e;
49 if (front == tail)//判断是否满了
50 doubleCapacity();
51 }
52
53 public void addLast(E e) {
54 //添加到最后一个,这个方法和addFirst有很明显的不同,
55 // addFirst是添加的时候就要计算front的位置,而addLast
56 // 方法是存值之后在计算tail的,/因为tail位置是没有
57 // 存值的,他表示的末端元素的下一个,是空,所以存值之后
58 //要计算tail的值
59 data[tail] = e;
60 tail = (tail + 1) % data.length;
61 if (tail == front)//判断是否满
62 doubleCapacity();
63 }
64
65 public E removeFirst() {//删除第一个
66 if (isEmpty())
67 throw new IllegalStateException("队列是空的,无法移除……");
68 E result = (E) data[front];
69 data[front] = null;
70 // 删除第一个,这里的所有第一我们都认为是front所指的,
71 // 不是数组的0位置,然后在计算front的值
72 front = (front + 1) % data.length;
73 return result;
74 }
75
76 public E removeLast() {//删除最后一个
77 if (isEmpty())
78 throw new IllegalStateException("队列是空的,无法移除……");
79 tail = (tail - 1 + data.length) % data.length;
80 E result = (E) data[tail];
81 data[tail] = null;
82 return result;
83 }
84
85 public E peekFirst() {
86 if (isEmpty())
87 throw new IllegalStateException("队列是空的,无法获取……");
88 return (E) data[front];
89 }
90
91 public E peekLast() {
92 if (isEmpty())
93 throw new IllegalStateException("队列是空的,无法获取……");
94 return (E) data[(tail - 1 + data.length) % data.length];
95 }
96
97 public int size() {//元素的size
98 return (tail - front + data.length) % data.length;
99 }
100
101 //是否为空,在上面添加元素的时候也可能front==tail,当添加
102 // 元素之后front==tail的时候就认为是满了,然后扩容,重新
103 // 调整front和tail的值,所以扩容之后front就不可能等于tail。
104 //如果没有触发上面添加元素的时候front等于tail我们就认为他是空的。
105 public boolean isEmpty() {
106 return front == tail;
107 }
108}
代码中都有详细的注释,就不在过多介绍。